//class Solution {
//public:
//    Node* copyRandomList(Node* head)
//    {
//        Node* cur = head;
//        Node* phead = nullptr;
//        Node* ptail = nullptr;
//
//        map<Node*, Node*> m;
//        while (cur)
//        {
//            Node* temp = new Node(cur->val);
//            if (phead == nullptr)
//            {
//                phead = ptail = temp;
//            }
//            else
//            {
//                ptail->next = temp;
//                ptail = ptail->next;
//            }
//
//            m[cur] = temp;
//            cur = cur->next;
//        }
//
//        cur = head;
//        while (cur)
//        {
//            Node* copy = m[cur];
//
//            if (cur->random == nullptr)
//                copy->random = nullptr;
//            else
//                copy->random = m[cur->random];
//
//            cur = cur->next;
//        }
//
//        return phead;
//    }
//};